package LeetCode.字符串;

/**
 * @Project: data-structure-and-algorithms
 * @Package: LeetCode.字符串
 * @ClassName: t14
 * @Author: zhouyihe
 * @Date: 2025/11/3 14:40
 * @Description: 最长公共前缀
 */
public class t14 {
    public static void main(String[] args) {
        String[] strs = {"flower", "flow", "flight"};
        System.out.println(longestCommonPrefix(strs));
        System.out.println(longestCommonPrefix1(strs));
        System.out.println(longestCommonPrefix2(strs));
        // System.out.println(longestCommonPrefix3(strs));

    }

    public static String longestCommonPrefix(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String res = strs[0];
        for (int i = 1; i < strs.length; i++) {
            while (strs[i].indexOf(res) != 0) {
                res = res.substring(0, res.length() - 1);
                if (res.isEmpty()) {
                    return "";
                }
            }
        }
        return res;
    }

    // 横向扫描
    public static String longestCommonPrefix1(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        String prefix = strs[0];
        for (int i = 1; i < strs.length; i++) {
            prefix = longestCommonPrefix(prefix, strs[i]);
            if (prefix.isEmpty()) {
                break;
            }
        }
        return prefix;
    }

    /**
     * 查找两个字符串的最长公共前缀
     *
     * @param str1 第一个字符串
     * @param str2 第二个字符串
     * @return 返回两个字符串的最长公共前缀，如果没有公共前缀则返回空字符串
     */
    public static String longestCommonPrefix(String str1, String str2) {
        // 获取两个字符串中较短的长度，避免越界访问
        int length = Math.min(str1.length(), str2.length());
        int index = 0;

        // 从头开始逐个比较字符，直到遇到不匹配的字符或到达较短字符串的末尾
        while (index < length && str1.charAt(index) == str2.charAt(index)) {
            index++;
        }

        // 返回公共前缀部分
        return str1.substring(0, index);
    }


    // 纵向扫描
    public static String longestCommonPrefix2(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        for (int i = 0; i < strs[0].length(); i++) {
            char c = strs[0].charAt(i);
            for (int j = 1; j < strs.length; j++) {
                if (i == strs[i].length() || strs[j].charAt(i) != c) {
                    return strs[0].substring(0, i);
                }
            }
        }
        return strs[0];
    }

    // 分治
    public static String longestCommonPrefix3(String[] strs) {
        if (strs.length == 0) {
            return "";
        } else {
            return longestCommonPrefix3(strs, 0, strs.length - 1);
        }
    }

    private static String longestCommonPrefix3(String[] strs, int start, int end) {
        if (start == end) {
            return strs[start];
        } else {
            int mid = start + ((end - start) >> 1);
            String left = longestCommonPrefix3(strs, start, mid);
            String right = longestCommonPrefix3(strs, mid + 1, end);
            // 调用比对两个字符串的公共前缀方法
            return longestCommonPrefix(left, right);
        }
    }

    // 查找.二分查找
    public static String longestCommonPrefix4(String[] strs) {
        if (strs.length == 0) {
            return "";
        }
        int minLength = Integer.MAX_VALUE;
        for(String str: strs){
            minLength = Math.min(minLength, str.length());
        }
        int low = 0, high = minLength;
        while(low < high){
            int mid = (low + high + 1) >> 1 + low;
            if(isCommonPrefix(strs, mid)){
                low = mid;
            }else{
                high = mid - 1;
            }
        }

        return strs[0].substring(0, low);
    }

    private static boolean isCommonPrefix(String[] strs, int length) {
        String str0 = strs[0].substring(0, length);
        int count = strs.length;
        for (int i = 1; i < count; i++) {
            String str = strs[i];
            for (int j = 0; j < length; j++) {
                if (str0.charAt(j) != str.charAt(j)) {
                    return false;
                }
            }
        }
        return true;
    }
}
